use stdx::default::default;
use stdx::iter::IteratorExt as _;

use std::collections::BTreeMap;
use std::collections::HashMap;
use std::iter::once;

use serde::de::Visitor;
use serde::Deserialize;
use serde::Deserializer;

pub fn count_provinces(data_path: &str) -> String {
    let data: Data = {
        let content = std::fs::read_to_string(data_path).unwrap();
        serde_json::from_str(&content).unwrap()
    };

    data.values().map(solve).join_(",")
}

fn solve(cities: &Cities) -> u32 {
    let mut name_map = NameMap::default();
    let mut uf = UnionFind::default();

    for (key, values) in &cities.0 {
        for name in once(key).chain(values.iter()) {
            if let Some(id) = name_map.visit(name) {
                uf.visit(id);
            }
        }
        for value in values {
            uf.union_(name_map.get(key), name_map.get(value));
        }
    }

    uf.count_roots() as u32
}

type Data = BTreeMap<String, Cities>;

#[derive(Debug)]
struct Cities(Vec<(String, Vec<String>)>);

impl<'de> Deserialize<'de> for Cities {
    fn deserialize<D>(deserializer: D) -> Result<Cities, D::Error>
    where
        D: Deserializer<'de>,
    {
        struct CitiesVisitor;

        impl<'de> Visitor<'de> for CitiesVisitor {
            type Value = Vec<(String, Vec<String>)>;

            fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
                formatter.write_str("a map")
            }

            fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
            where
                A: serde::de::MapAccess<'de>,
            {
                let mut cities: Self::Value = default();
                while let Some((key, value)) = map.next_entry()? {
                    cities.push((key, value));
                }
                Ok(cities)
            }
        }

        Ok(Cities(deserializer.deserialize_map(CitiesVisitor)?))
    }
}

#[derive(Default)]
struct NameMap {
    id2name: HashMap<u32, String>,
    name2id: HashMap<String, u32>,
}

impl NameMap {
    fn visit(&mut self, name: &str) -> Option<u32> {
        if self.name2id.contains_key(name) {
            return None;
        }
        let id = (self.id2name.len() + 1) as u32;
        self.id2name.insert(id, name.to_owned());
        self.name2id.insert(name.to_owned(), id);
        Some(id)
    }

    fn get(&self, name: &str) -> u32 {
        self.name2id[name]
    }
}

#[derive(Default)]
struct UnionFind {
    root: HashMap<u32, u32>,
}

impl UnionFind {
    fn visit(&mut self, id: u32) {
        self.root.insert(id, id);
    }

    fn find(&mut self, id: u32) -> u32 {
        let root = self.root[&id];
        if root == id {
            return root;
        }
        let root = self.find(root);
        self.root.insert(id, root);
        root
    }

    fn union_(&mut self, from_: u32, to: u32) {
        let from = self.find(from_);
        let to = self.find(to);
        if from != to {
            self.root.insert(from, to);
        }
    }

    fn count_roots(&self) -> usize {
        let mut count = 0;
        for (id, root) in &self.root {
            if id == root {
                count += 1;
            }
        }
        count
    }
}
